Leetcode Array

Contents

1. 1. Leetcode 4. Median of Two Sorted Arrays
2. 2. Leetcode 11. Container With Most Water
3. 3. Leetcode 16. 3Sum Closest
4. 4. Leetcode 18. 4Sum
5. 5. Leetcode 35. Search Insert Position
6. 6. Leetcode 41. First Missing Positive
7. 7. Leetcode 45. Jump Game II
8. 8. Leetcode 55. Jump Game
9. 9. Leetcode 59. Spiral Matrix II
10. 10. Leetcode 63. Unique Paths II
11. 11. Leetcode 64. Minimum Path Sum
12. 12. Leetcode 66. Plus One
13. 13. Leetcode 73. Set Matrix Zeroes
14. 14. Leetcode 74. Search a 2D Matrix
15. 15. Leetcode 78. Subsets

Leetcode 4. Median of Two Sorted Arrays

求两个已排序数组的中位数

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	total_length := len(nums1) + len(nums2)
	if total_length == 0 {
		return 0
	}
	median_pos := (len(nums1) + len(nums2)) / 2
	p1, p2, median_1, median_2, counter, tmp := 0, 0, 0, 0, 0, 0
	var ans float64
	for {
		if p1 >= len(nums1) && p2 >= len(nums2) {
			break
		}
		if p1 >= len(nums1) {
			tmp = nums2[p2]
			p2 += 1
		} else if p2 >= len(nums2) {
			tmp = nums1[p1]
			p1 += 1
		} else if nums1[p1] <= nums2[p2] {
			tmp = nums1[p1]
			p1 += 1
		} else if nums1[p1] > nums2[p2] {
			tmp = nums2[p2]
			p2 += 1
		}

		if counter == (median_pos - 1) {
			median_2 = tmp
		}
		if counter == median_pos {
			median_1 = tmp
			if total_length%2 == 0 {
				ans = float64((median_1 + median_2)) / 2
				break
			} else {
				ans = float64(median_1)
				break
			}
		}
		counter++
	}
	return ans
}

Leetcode 11. Container With Most Water

求解能装最多水的容器，体积等于两边缘的距离乘以较短边的长度。两个指针分列于左右

然后向中间搜索即可，计算每次所取容器的体积并更新历史最大值。

func min(A int, B int) int {
	if A < B {
		return A
	} else {
		return B
	}
}

func maxArea(height []int) int {
	size := len(height)
	left, right := 0, size-1
	max := 0
	for {
		if left >= right {
			break
		}
		dis := min(height[left], height[right]) * (right - left)
		if max < dis {
			max = dis
		}
		if height[left] <= height[right] {
			left += 1
		} else if height[left] > height[right] {
			right -= 1
		}
	}
	return max
}

Leetcode 16. 3Sum Closest

暴力循环更新与target最近的搭配

func threeSumClosest(nums []int, target int) int {
	sort.Ints(nums)
	diff := math.MaxInt64
	var l, r, val, dis, res int
	for i := 0; i < len(nums)-2; i++ {
		l = i + 1
		r = len(nums) - 1
		for {
			if l >= r {
				break
			}
			val = nums[i] + nums[l] + nums[r]
			dis = int(math.Abs(float64(val - target)))
			if dis == 0 {
				return target
			} else if diff > dis {
				diff = dis
				res = val
			}

			if val < target {
				l++
			} else {
				r--
			}
		}
	}
	return res
}

Leetcode 18. 4Sum

​排序后，先确定两个数，然后从两边暴力搜索剩下两数即可。。。 时间复杂度为 O(n^3) ，可以做剪枝优化

func fourSum(nums []int, target int) [][]int {
	ans := make([][]int, 0, 10)
	if nums == nil || len(nums) < 4 {
		return ans
	}
	sort.Ints(nums)
	fmt.Println(nums)
	for i := 0; i < len(nums); i++ {
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		tmp := target - nums[i]
		for j := i + 1; j < len(nums)-2; j++ {
			if j > i+1 && nums[j] == nums[j-1] {
				continue
			}
			tmp1 := tmp - nums[j]
			left, right := j+1, len(nums)-1
			for {
				if left >= right {
					break
				}

				if nums[left]+nums[right] == tmp1 {
					ans = append(ans, []int{nums[i], nums[j], nums[left], nums[right]})
					for {
						left += 1
						if left < right && nums[left] == nums[left-1] {
							continue
						} else {
							break
						}
					}

					for {
						right -= 1
						if left < right && nums[right] == nums[right+1] {
							continue
						} else {
							break
						}
					}
				} else if nums[left]+nums[right] < tmp1 {
					for {
						left += 1
						if left < right && nums[left] == nums[left-1] {
							continue
						} else {
							break
						}
					}
				} else if nums[left]+nums[right] > tmp1 {
					for {
						right -= 1
						if left < right && nums[right] == nums[right+1] {
							continue
						} else {
							break
						}
					}
				}

			}

		}
	}
	return ans
}

Leetcode 35. Search Insert Position

查找有序插入的位置，水题

func searchInsert(nums []int, target int) int {
    for i := 0; i < len(nums); i++ {
        if nums[i] == target || nums[i] > target {
            return i
        } else if nums[i] < target && i < len(nums) - 1 && nums[i+1] > target {
            return i + 1
        }
    }
    return len(nums)
}

Leetcode 41. First Missing Positive

Note: Your algorithm should run in O(n) time and uses constant extra space.

由于原题要求O(n)的时间复杂度，所以无法使用传统的排序算法，唯一能用的是桶排序。然而题目又要求常数级的空间复杂度，所以借助原数组空间，同时使用swap来实现桶排序即可。

func firstMissingPositive(nums []int) int {
	for i := range nums {
		for nums[i] > 0 && nums[i] <= len(nums) && nums[i] != nums[nums[i]-1] {
			nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
		}
	}
	for i := range nums {
		if nums[i] != i+1 {
			return i + 1
		}
	}
	return len(nums) + 1
}

Leetcode 45. Jump Game II

贪心算法。和Leetcode 55 同样是O(n)解法，唯一不同是要记录每一段的最大跳跃值tmp_MaxIndex，找出这一区间内的最大跳跃值作为下一区间的max_index，区间的数量就等于最优解的跳跃数

func jump(nums []int) int {
	max_index := nums[0]
	if len(nums) == 1 {
		return 0
	}
	tmp_MaxIndex := max_index
	jump_cnt := 0
	for index, v := range nums {
		if index+v > tmp_MaxIndex {
			tmp_MaxIndex = index + v
		}
		if index == max_index || index == len(nums)-1 {
			jump_cnt += 1
			max_index = tmp_MaxIndex
		}
	}
	return jump_cnt
}

Leetcode 55. Jump Game

O(n)解法，记录比较当前位置能去到的最远点，并更新所有目前已知点能去到的最远点。对每一个点都做这样的更新，看最后能否到达终点即可。

func canJump(nums []int) bool {
	index := 0
	max_index := nums[0]
	for index <= max_index && index < len(nums) {
		if index+nums[index] > max_index {
			max_index = index + nums[index]
		}
		index += 1
	}
    
	if index == len(nums) {
		return true
	} else {
		return false
	}
}

Leetcode 59. Spiral Matrix II

漩涡数字矩形。打表题，判断行数列数，按螺旋形的顺序对位填入相应的数字即可。

func generateMatrix(n int) [][]int {
	matrix := make([][]int, n)
	for i := range matrix {
		matrix[i] = make([]int, n)
	}
	if n <= 0 {
		return matrix
	}
	index := 1
	for i := 0; i < (n-1)/2+1; i++ {
		row := i
		col := i
		for col < n-i {               //右移
			matrix[row][col] = index
			index++
			col++
		}
		col--
		for row = i + 1; row < n-i; row++ {      //下移
			matrix[row][col] = index
			index++
		}
		row--
		for col = n - i - 2; col > i; col-- {    //左移
			matrix[row][col] = index
			index++
		}
		for row = n - i - 1; row > i; row-- {    //上移
			matrix[row][col] = index
			index++
		}
	}
	return matrix
}

Leetcode 63. Unique Paths II

图寻路，只有向右以及向下两个方向。直接暴力DFS，超时！再看题，发现数据量为n,m <= 100，显然用不了搜索算法。路径数问题求解尝试用dp。从(0,0)出发，起点路径数首先置为1，遍历每个点，可达路径数 = 左邻点可达路径数 + 上邻点可达路径数，当然首行首列要做判断，如遇路障此点可达路径数直接置0

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
	if obstacleGrid == nil || obstacleGrid[0][0] == 1 {
		return 0
	}
	route_matrix := make([][]int, len(obstacleGrid))
	for i := range route_matrix {
		route_matrix[i] = make([]int, len(obstacleGrid[0]))
	}
	for i := range obstacleGrid {
		for j := range obstacleGrid[0] {
			if i == 0 && j == 0 {
				route_matrix[i][j] = 1
			} else if obstacleGrid[i][j] == 1 {
				route_matrix[i][j] = 0
			} else if i == 0 {
				route_matrix[i][j] = route_matrix[i][j-1]
			} else if j == 0 {
				route_matrix[i][j] = route_matrix[i-1][j]
			} else {
				route_matrix[i][j] = route_matrix[i][j-1] + route_matrix[i-1][j]
			}
		}
	}
	return route_matrix[len(obstacleGrid)-1][len(obstacleGrid[0])-1]
}

Leetcode 64. Minimum Path Sum

与63一样，直接dp求解，dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

func min_int(A int, B int) int {
	if A > B {
		return B
	} else {
		return A
	}
}

func minPathSum(grid [][]int) int {
	if grid == nil {
		return 0
	}
	matrix := make([][]int, len(grid))
	for i := range matrix {
		matrix[i] = make([]int, len(grid[0]))
		for j := range matrix[i] {
			matrix[i][j] = math.MaxInt64
		}
	}
	for i := range grid {
		for j := range grid[i] {
			if i == 0 && j == 0 {
				matrix[i][j] = grid[i][j]
			} else if i == 0 {
				matrix[i][j] = matrix[i][j-1] + grid[i][j]
			} else if j == 0 {
				matrix[i][j] = matrix[i-1][j] + grid[i][j]
			} else {
				matrix[i][j] = min_int(matrix[i-1][j], matrix[i][j-1]) + grid[i][j]
			}
		}
	}
	return matrix[len(grid)-1][len(grid[0])-1]
}

Leetcode 66. Plus One

高精度加法

func plusOne(digits []int) []int {
	len := len(digits)
	res := 0
	for i := len - 1; i >= 0; i-- {
		if i == len-1 {
			digits[i] += (res + 1)
		} else {
			digits[i] += res
		}
		res = digits[i] / 10
		digits[i] %= 10
	}
	if res != 0 {
		return append([]int{res}, digits...)
	} else {
		return digits
	}
}

Leetcode 73. Set Matrix Zeroes

要求用常数的额外空间，即只能在原存储数组中进行操作，不能开辟任意的额外空间。所以先对首行首列进行判断，判断之后利用首行首列的空间来存储对应行列的置零情况。

func setZeroes(matrix [][]int) {
	var first_row, first_col bool = false, false

    //首行首列判断
	for i := range matrix {
		if matrix[i][0] == 0 {
			first_col = true
		}
	}
	for j := range matrix[0] {
		if matrix[0][j] == 0 {
			first_row = true
		}
	}

    //判断值存储
	for i := range matrix {
		for j := range matrix[0] {
			if matrix[i][j] == 0 && i != 0 && j != 0 {
				matrix[i][0] = 0
				matrix[0][j] = 0
			}
		}
	}
    
    //非首行首列赋值
	for i := range matrix {
		if matrix[i][0] == 0 && i != 0 {
			for j := range matrix[0] {
				matrix[i][j] = 0
			}
		}
	}
	for j := range matrix[0] {
		if matrix[0][j] == 0 && j != 0 {
			for i := range matrix {
				matrix[i][j] = 0
			}
		}
	}
    
    //首行首列赋值
	if first_row {
		for j := range matrix[0] {
			matrix[0][j] = 0
		}
	}
	if first_col {
		for i := range matrix {
			matrix[i][0] = 0
		}
	}
}

Leetcode 74. Search a 2D Matrix

由于是排好序的，直接检索行首行末从而确定当前行的范围，在范围内才进行搜索。时间复杂度为o(m+n)也可通过，麻烦一点的话可以用二分法来检索，时间复杂度为o(logm + logn)

func searchMatrix(matrix [][]int, target int) bool {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return false
    }
	for i := range matrix {
		if matrix[i][0] <= target && matrix[i][len(matrix[0])-1] >= target {
			for j := range matrix[0] {
				if matrix[i][j] == target {
					return true
				}
			}
            return false
		}
	}
	return false
}

Leetcode 78. Subsets

经典子集问题，DFS遍历即可。

var ans [][]int

func subsets(nums []int) [][]int {
	if len(nums) == 0 {
		return ans
	}
	ans = make([][]int, 0)
	path := []int{}
	tmp_path := []int{}
	copy(tmp_path, path)
	ans = append(ans, tmp_path)
	dfs(nums, 0, path)
	return ans
}

func dfs(nums []int, pos int, path []int) {
	if pos == len(nums) {
		return
	}
	for i := pos; i < len(nums); i++ {
		var t int = nums[i]
		path = append(path, t)
		
		tmp_path := make([]int, len(path))
		copy(tmp_path, path)
		ans = append(ans, tmp_path)
		
		dfs(nums, i+1, path)
		
		path = path[:len(path)-1]
	}
}

​